W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
After a new administrative division of Byteland cartographic office works on a new demographic map of the country. Because of technical reasons only a few colors can be used. The map should be colored so that regions with the same or similar population (number of inhabitants) have the same color. For a given color let be the number, such that:
A coloring error of a region marked with color is an absolute value of the difference between and the region's population. A cumulative error is a sum of coloring errors of all regions. We are looking for an optimal coloring of the map (the one with the minimal cumulative error).
Write a program which:
In the first line of the standard input an integer is written, which is the number of regions in Byteland, . In the second line the number denoting the number of colors used to color the map is written, . In each of the following lines there is one non-negative integer - a population of one of the regions of Byteland. No population exceeds .
Your program should write in the only line of the standard output one integer number equal to a minimal cumulative error, which can be achieved while the map is colored (optimally).
For the input data:
11 3 21 14 6 18 10 2 15 12 3 2 2
the correct result is:
15
Task author: Marcin Sawicki.